#include "graph.h"
using namespace std;

Graph::Graph(int V)
{
    //初始化点数
    this->V=V;
    //新建二维矩阵保存各点
    this->matrix=new int*[V];
    for(int i=0;i<V;i++)
    {
        matrix[i]=new int[V];
        //memset(matrix[i],0,sizeof(matrix[i]));
        for(int j=0;j<V;j++)
            matrix[i][j]=0;
    }
    color=new int[V];
    dist=new int[V];
    pai=new int[V];
    disc=new int[V];
    finish=new int[V];
    topo=new int[V];
}

Graph::~Graph()
{
    delete color;
    delete dist;
    delete pai;
    for(int i=0;i<V;i++)
        delete[] matrix[i];
    delete disc;
    delete finish;
    delete topo;
}
void
Graph::addEdge(int start,int end,int weight,bool single)
{
    this->matrix[start][end]=weight;
    if(!single)
        this->matrix[end][start]=weight;
}

bool
Graph::adjecent(int a,int b)
{
    return matrix[a][b]!=0;
}

void
Graph::printMap()
{
    for(int i=0;i<V;i++)
    {
        for(int j=0;j<V;j++)
        {
            cout<<matrix[i][j]<<"\t";
        }
        cout<<endl;
    }
}

void 
Graph::BFS(int s)
{
    //各数据的初始化
    for(int i=0;i<V;i++)
    {
        color[i]=WHITE;
        dist[i]=INF;
        pai[i]=NIL;
    }
    //起点标灰，距离设0，前驱设为-1
    color[s]=GRAY;
    dist[s]=0;
    pai[s]=NIL;
    queue<int> queue;//队列
    queue.push(s);//推入起点
    //当队列不为空时执行
    while(!queue.empty())
    {
         int cur=queue.front();
         queue.pop();
         for(int i=0;i<V;i++)   //遍历当前点的邻接点
         {
            if(adjecent(cur,i)) 
            {
                if(color[i]==WHITE) //如果邻接点尚未走到
                {
                    color[i]=GRAY;  //涂灰
                    dist[i]=dist[cur]+1;    //距离加一
                    pai[i]=cur; //设置该点前驱节点为当前点
                    queue.push(i);  //推入队列
                }
            }
         }
         color[cur]=BLACK;  //将当前点设为黑色
    }
}

void
Graph::printBFS()
{
    cout<<"源点到各点距离"<<endl;
    for(int i=0;i<V;i++)
        cout<<dist[i]<<" ";
    cout<<endl;
    cout<<"各点前驱"<<endl;
    for(int i=0;i<V;i++)
        cout<<pai[i]<<" ";
    cout<<endl;

}

void
Graph::DFS_VISIT(int u)
{
    time++; //时间增加
    disc[u]=time;   //设置当前处理的点的发现时间
    color[u]=GRAY;  //表示正在处理该点
    for(int i=0;i<V;i++) //处理所有邻边
    {
        if(adjecent(u,i))
        {
            if(color[i]==WHITE)
            {
                pai[i]=u;   //设置前驱为当前节点
                DFS_VISIT(i);   //递归处理
            }
        }
    }
    color[u]=BLACK;
    time++; //时间增加
    finish[u]=time;//设置完成时间
    topo[topoIndex++]=u;    //将完成的点加入到拓扑排序数组中
}

void
Graph::DFS()
{
    topoIndex=0;    //初始化拓扑排序数组索引
    for(int i=0;i<V;i++)    //初始化原始颜色、前驱
    {
        color[i]=WHITE;
        pai[i]=NIL;
    }
    time=0; //初始化时间
    for(int i=0;i<V;i++)
    {
        if(color[i]==WHITE) //如果某个点没有处理到
            DFS_VISIT(i);   //处理这个点
    }
}

void
Graph::printDFS()
{
    cout<<"各点的发现时间为"<<endl;
    for(int i=0;i<V;i++)
        cout<<disc[i]<<" ";
    cout<<endl;
    cout<<"各点的结束时间为"<<endl;
    for(int i=0;i<V;i++)
        cout<<finish[i]<<" ";
    cout<<endl;
    cout<<"各点的前驱节点为"<<endl;
    for(int i=0;i<V;i++)
        cout<<pai[i]<<" ";
    cout<<endl;
}

void
Graph::printTopo()
{
    cout<<"拓扑排序结果如下："<<endl;
    for(int i=0;i<V;i++)
    {
        cout<<topo[V-i-1]<<(i==V-1?"\n":"->");
    }
}

